package com.tgy.programmer_code_interview_guide._01_stack_queue;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 1/19/21 9:44 AM
 */
public class _07_构造数组的MaxTree {

    public static Node generalArrayMaxTree(int[] arrs) {

        if (arrs == null || arrs.length == 0) {

            return null;
        }

        Node[] nodes = new Node[arrs.length];

        for (int i = 0; i < arrs.length; i++) {

            nodes[i] = new Node(arrs[i]);
        }

        Stack<Node> stack = new Stack<>();

        Map<Node,Node> leftMap = new HashMap<>();
        Map<Node,Node> rightMap = new HashMap<>();

        for (int i = 0; i < nodes.length; i++) {

            Node node = nodes[i];
            if (stack.isEmpty()) {
                stack.push(node);
                continue;
            }

            if (stack.peek().value > nodes[i].value) {

                leftMap.put(node,stack.peek());
                stack.push(node);
                continue;
            }

            while (!stack.isEmpty() && stack.peek().value < node.value) {

                Node tmpNode = stack.pop();
                rightMap.put(tmpNode,node);
            }
            stack.push(node);
        }

        while (!stack.isEmpty()) {

            Node node = stack.pop();

            if (!stack.isEmpty()) {

                leftMap.put(node,stack.peek());
            }
        }

        Node head = null;

        for (int i = 0; i < nodes.length; i++) {

            Node node = nodes[i];

            Node leftNode = leftMap.get(node);
            Node rightNode = rightMap.get(node);

            if (leftNode == null && rightNode == null) {

                head = node;
            }else if (leftNode == null) {

                if (rightNode.left == null) {

                    rightNode.left = node;
                }else {

                    rightNode.right = node;
                }
            }else if (rightNode == null) {

                if (leftNode.right == null) {

                    leftNode.right = node;
                }else {
                    leftNode.left = node;
                }
            }else {

                Node parent = leftNode.value < rightNode.value ? leftNode:rightNode;

                if (parent.left != null) {

                    parent.left = node;
                }else {

                    parent.right = node;
                }
            }

        }

        return head;
    }

    public static void main(String[] args) {

//       Node root = generalArrayMaxTree(new int[]{4,2,5,1,3});
       Node root = generalArrayMaxTree(new int[]{3,4,5,1,2});

        System.out.println(root);
    }
}
